Jason O'Kane

University of South Carolina

Computer Science and Engineering

 

There is no need to build good robots.

 

The classic algorithm for minimal design looks like this:

1. Think of a problem. Call it $x$.
2. Hire a good graduate student to work on $x$.
3. Wait at least a few months.
4. Success!

. . . Can we automate this process?

Algorithms for general-purpose robot design problems would be great. . .

. . . but all of the interesting questions are NP-hard.

Given a filter expressed as a transition graph:

• Edges are labeled with observations.
• Vertices ("states") are labeled with outputs that define a task.

 

We want to find:

• the smallest filter that produces
• the same output for
• all plausible observation strings.

 

Reminder from analysis of algorithms:

For an algorithm that runs in $O(2^n)$ time, holding time fixed and increasing computer speed from $x$ to $2x$, we increase the size of problems we can solve from $n$ to $n+1$.

We dream about this: